Search for: All records

We study two biased Maker-Breaker games played on the complete digraph $$\vec{K}_n$$. In the strong connectivity game, Maker wants to build a strongly connected subgraph. We determine the asymptotic optimal bias for this game viz. $$\frac{n}{\log n}$$. In the Hamiltonian game, Maker wants to build a Hamiltonian subgraph. We determine the asymptotic optimal bias for this game up to a constant factor. 

Let $${\bf A}$$ be an $$n\times m$$ matrix over $$\mathbf{GF}_2$$ where each column consists of $$k$$ ones, and let $$M$$ be an arbitrary fixed binary matroid. The matroid growth rate theorem implies that there is a constant $$C_M$$ such that $$m\geq C_M n^2$$ implies that the binary matroid induced by {\bf A} contains $$M$$ as a minor. We prove that if the columns of $${\bf A}={\bf A}_{n,m,k}$$ are chosen \emph{randomly}, then there are constants $$k_M, L_M$$ such that $$k\geq k_M$$ and $$m\geq L_M n$$ implies that $${\bf A}$$ contains $$M$$ as a minor w.h.p. 

We consider arbitrary graphs $$G$$ with $$n$$ vertices and minimum degree at least $$\delta n$$ where $$\delta>0$$ is constant.\\ (a) If the conductance of $$G$$ is sufficiently large then we obtain an asymptotic expression for the cover time $$C_G$$ of $$G$$ as the solution to an explicit transcendental equation.\\ (b) If the conductance is not large enough to apply (a), but the mixing time of a random walk on $$G$$ is of a lesser magnitude than the cover time, then we can obtain an asymptotic deterministic estimate via a decomposition into a bounded number of dense subgraphs with high conductance. \\ (c) If $$G$$ fits neither (a) nor (b) then we give a deterministic asymptotic (2+o(1))-approximation of $$C_G$$. 

Let $$\Omega_q$$ denote the set of proper $[q]$-colorings of the random graph $$G_{n,m}, m=dn/2$$ and let $$H_q$$ be the graph with vertex set $$\Omega_q$$ and an edge $$\set{\s,\t}$$ where $$\s,\t$$ are mappings $$[n]\to[q]$$ iff $$h(\s,\t)=1$$. Here $$h(\s,\t)$$ is the Hamming distance $$|\set{v\in [n]:\s(v)\neq\t(v)}|$$. We show that w.h.p. $$H_q$$ contains a single giant component containing almost all colorings in $$\Omega_q$$ if $$d$$ is sufficiently large and $$q\geq \frac{cd}{\log d}$$ for a constant $c>3/2$. 

The classical Beardwood-Halton-Hammersly theorem (1959) asserts the existence of an asymptotic formula of the form $$\beta \sqrt n$$ for the minimum length of a Traveling Salesperson Tour throuh $$n$$ random points in the unit square, and in the decades since it was proved, the existence of such formulas has been shown for other such \emph{Euclidean functionals} on random points in the unit square as well. Despite more than 50 years of attention, however, it remained unknown whether the minimum length TSP through $$n$$ random points in $[0,1]^2$ was asymptotically distinct from its natural lower bounds, such as the minimum length spanning tree, the minimum length 2-factor, or, as raised by Goemans and Bertsimas, from its linear programming relaxation. We prove that the TSP on random points in Euclidean space is indeed asymptotically distinct from these and other natural lower bounds, and show that this separation implies that branch-and-bound algorithms based on these natural lower bounds must take nearly exponential ($$e^{\tilde \Omega(n)}$$) time to solve the TSP to optimality, even in average case. This is the first average-case superpolynomial lower bound for these branch-and-bound algorithms (a lower bound as strong as $$e^{\tilde \Omega (n)}$$ was not even been known in worst-case analysis).